package exams.dp;

import java.util.*;

public class StrMatchSolution {

    /**
     * 正则表达式匹配
     *
     * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
     * 1.模式中的字符'.'表示任意一个字符
     * 2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。
     * 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
     *
     * 数据范围:
     * 1.str 只包含从a-z的小写字母。
     * 2.pattern 只包含从a-z的小写字母以及字符.和*，无连续的'*'。
     * 3.0≤str.length≤26
     * 4.0≤pattern.length≤26
     * */
    public boolean match (String str, String pattern) {
        // write code here
        int len1 = str.length();
        int len2 = pattern.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];

        for(int i=0; i<=len1; i++) {
            for(int j =0; j<=len2; j++) {
                if(j == 0) {
                    if(i == 0) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = false;
                    }
                } else {
                    if(pattern.charAt(j - 1) != '*') {
                        if(i > 0 && (str.charAt(i - 1) == pattern.charAt(j -1) || pattern.charAt(j-1) == '.')) {
                            dp[i][j] = dp[i-1][j-1];
                        }
                    } else {
                        if(j>=2) {
                            dp[i][j] = dp[i][j] || dp[i][j-2];
                        }
                        if(i>0 && j>= 2 &&(str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j - 2) == '.')) {
                            dp[i][j] = dp[i][j] || dp[i-1][j];
                        }
                    }
                }
            }
        }

        return dp[len1][len2];
    }

    /**
     * 最长的括号子串
     *
     * 给出一个长度为 n的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
     *
     * 例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
     * 例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
     *
     * 字符串长度：0≤n≤5∗105
     *
     * 要求时间复杂度O(n),空间复杂度O(n).
     * */
    public int longestValidParentheses (String s) {
        // write code here
        int res = 0;
        int start = -1;
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        for(int i =0; i< s.length(); i++) {
            char curs = s.charAt(i);
            if(curs == '(') {
                stack.push(i);
            } else {
                if(stack.isEmpty()) {
                    start = i;
                } else {
                    stack.pop();
                    if(stack.isEmpty()) {
                        res = Math.max(res, i - start);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                }

            }
        }

        return res;
    }
}
